package LearnAlgorithm.e_多维数组and矩阵;

public class d二维正方01数组求最大1围成的正方形 {
	public static void main(String[] args) {
		int[][] matrix = new int[][] {
			{1,1,1,1},
			{1,0,0,1},
			{1,0,0,1},
			{1,1,1,1},
		};
		long before = System.currentTimeMillis();
		int findMaxSquare = findMaxSquare(matrix, matrix.length);
		util.Util.duration(before);
		System.out.println(findMaxSquare);
	}
	
	/**
	 * O(N^4)
	 * @param matrix
	 * @param matrixLength
	 * @return
	 */
	public static int findMaxSquare(int[][] matrix, int matrixLength) {
		int squareLegth = matrixLength;//默认矩阵长度是最大正方形长度；
		while (squareLegth > 0) {//循环，只要正方形长度>0
			for (int row = 0; row < matrixLength; row++) {//1逐个元素作为顶点
				if (row + (squareLegth - 1) > (matrixLength - 1)) {//如果此顶点的某一个伸展方向不足以构成当前squareLength长度的正方形
					break;//那么直接大跳出循环
				}
				l3://这个是循环标签
					/*
					 退出多重循环的办法---通过break标签跳出多重循环
				 	Java定义的标签一定要紧跟在循环前
					 同时标签名后是冒号:
					 */
				for (int col = 0; col < matrixLength; col++) {//2以顶点进行四条边伸展判断
					if (col + (squareLegth - 1) > (matrixLength - 1)) {//如果此顶点的某一个伸展方向不足以构成当前squareLength长度的正方形
						break;//那么直接大跳出循环
					}
					int edgeRow = row;
					int edgeCol = col;
					while (edgeCol < col + squareLegth) {//上边界伸展判断；上边长度(col+squareLength)-edgeCol
						if (matrix[edgeRow][edgeCol] == 0) {//只要伸展过程中遇到0
							continue l3;//此顶点不符合，立即切换下一个顶点
						}
						edgeCol++;//没遇到0；继续伸展
					}
					edgeCol--;//复位；因为上一个循环跳出时edgeCol大小是(col+squareLength)
					while (edgeRow < row + squareLegth) {//右边界
						if (matrix[edgeRow][edgeCol] == 0) {
							continue l3;
						}
						edgeRow++;
					}
					edgeRow--;//复位
					while (edgeCol >= col) {//下边界
						if (matrix[edgeRow][edgeCol] == 0) {
							continue l3;
						}
						edgeCol--;
					}
					edgeCol++;//复位
					while (edgeRow >= row) {//左边界
						if (matrix[edgeRow][edgeCol] == 0) {
							continue l3;
						}
						edgeRow--;
					}
					return squareLegth;//走到这里就代表通过了层层判断，找到了最大正方形长度
				}
			}
			squareLegth--;
		}
		return 0;//没找到就返0
	}
}
